package 力扣_中等题;
/*
方法一：暴力解法
    l1 [9,9,9]
    l2[9,9]
    (1):res 接两链表之和。一个新的listNode；因为res是结果集，所以不能移动，用cur来代替
        digit：用来存相加后的十位数；total：存相加总和；
        首先l1第一个9 + l2第一个9 = 18  ；total=digital+18=0+18=18，所以存8进1
()
* */

//  Definition for singly-linked list.
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

 class 两数相加 {
    //暴力法
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode();
        ListNode cur = res;
        int digital = 0;
        while(l1 != null || l2 != null){//   或：||，两个有一个不为空就继续走
            int total = digital;//l1 l2 有一个不为null，就将total = digital
            if(l1 != null){
                total += l1.val;
                l1 = l1.next;
            }
            if(l2 != null){
                total += l2.val;
                l2 = l2.next;
            }
            digital = total / 10;
            cur.next = new ListNode(total%10);
            cur = cur.next;
        }
        if(digital !=0){//如果循环结束后还存在digital不为0；就继续加在cur上
            cur.next = new ListNode(digital);
        }
        return  res.next;
    }
     public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {//递归法（迭代法）
        //递归内存消耗较大，因为每一次递归实现系统都会重新为变量分配空间而不是覆盖原来的空间。递归次数多容易造成内存分配崩溃
        int total = l1.val + l2.val;
        int digital = total / 10;
        ListNode res = new ListNode(total % 10);
        if(l1.next != null || l2.next != null || digital != 0){
            l1 = l1.next != null ? l1.next : new ListNode(0);
            l2 = l2.next !=null ? l2.next : new ListNode(0);
            l1.val += digital;
            res.next = addTwoNumbers2(l1,l2);
        }
         return  res;
     }
}
/*
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 +

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */